
import std.math:abs,sqrt;
import maths.Misc:max;
import maths.Vec;

import TriPool;
import Renderer;

import std.stdio:writefln;


int orientation( int pX, int pY, int qX, int qY, int rX, int rY )
{
	int aX, aY, bX, bY;
	float d;

	aX = qX - pX;
	aY = qY - pY;

	bX = rX - pX;
	bY = rY - pY;

	d = cast(float)aX * cast(float)bY - cast(float)aY * cast(float)bX;
	return (d < 0) ? (-1) : (d > 0);
}

class Patch {

	this(int heightX, int heightY, int _worldX, int _worldY, int _mapSize, int _patchSize, int _varianceDepth, ubyte* hMap, TriPool _triPool){
		mapSize = _mapSize;
		patchSize = _patchSize;
		varianceDepth = _varianceDepth;
		triPool = _triPool;

		worldX = _worldX;
		worldY = _worldY;

		heightMap = &hMap[heightY * mapSize + heightX];

		varianceLeft = cast(ubyte*)malloc(ubyte.sizeof * (1<<varianceDepth));
		varianceRight = cast(ubyte*)malloc(ubyte.sizeof * (1<<varianceDepth));

		varianceDirty = true;
		reset();
	}

	void reset(){
		baseLeft.leftChild = baseRight.leftChild = null;
		baseLeft.rightChild = baseRight.rightChild = null;
		baseLeft.baseNeighbor = &baseRight;
		baseRight.baseNeighbor = &baseLeft;
		baseLeft.rightNeighbor = baseRight.rightNeighbor = null;
		baseLeft.leftNeighbor = baseRight.leftNeighbor = null;

		visible = false;
	}

	ubyte recursComputeVariance(int leftX, int leftY, ubyte leftZ,
								int rightX, int rightY, ubyte rightZ,
								int apexX, int apexY, ubyte apexZ, int node){
		int centerX = (leftX + rightX) >> 1;
		int centerY = (leftY + rightY) >> 1;
		ubyte myVariance;

		ubyte centerZ = heightMap[(centerY * mapSize) + centerX];
		
		assert(abs(5) == 5);
		assert(abs(-9) == 9);
		myVariance = abs(cast(int)centerZ - ((cast(int)leftZ + cast(int)rightZ)>>1));
		if( (abs(leftX - rightX) >= 8 ) || (abs(leftY - rightY) >= 8) ){
			myVariance = max!(ubyte)( myVariance, recursComputeVariance( apexX,   apexY,  apexZ, leftX, leftY, leftZ, centerX, centerY, centerZ,    node<<1 ) );
			myVariance = max!(ubyte)( myVariance, recursComputeVariance( rightX, rightY, rightZ, apexX, apexY, apexZ, centerX, centerY, centerZ, 1+(node<<1)) );
		}

		assert(currentVariance !is null);
		if(node < (1 << varianceDepth))
			currentVariance[node] = 1 + myVariance;

		return myVariance;
	}

	void computeVariance(){
		currentVariance = varianceLeft;
		recursComputeVariance(0, patchSize, heightMap[patchSize * mapSize],
				patchSize, 0, heightMap[patchSize],
				0, 0, heightMap[0], 1);
		currentVariance = varianceRight;
		recursComputeVariance(patchSize, 0, heightMap[patchSize],
				0, patchSize, heightMap[patchSize * mapSize],
				patchSize, patchSize, heightMap[patchSize * mapSize + patchSize], 1);
		varianceDirty = 0;
	}

	void setVisibility(int eyeX, int eyeY, int leftX, int leftY, int rightX, int rightY){
		int patchCenterX = worldX + patchSize / 2;
		int patchCenterY = worldY + patchSize / 2;
	
		visible = (orientation(eyeX, eyeY, rightX, rightY, patchCenterX, patchCenterY ) < 0) && (orientation(leftX, leftY, eyeX, eyeY, patchCenterX, patchCenterY) < 0);
	}

	void split(TriTreeNode *tri){
		if(tri.leftChild)
			return;

		if(tri.baseNeighbor && (tri.baseNeighbor.baseNeighbor !is tri) )
			split(tri.baseNeighbor);

		tri.leftChild  = triPool.newTri();
		tri.rightChild = triPool.newTri();

		if(!tri.leftChild)
			return;

		tri.leftChild.baseNeighbor = tri.leftNeighbor;
		tri.leftChild.leftNeighbor = tri.rightChild;

		tri.rightChild.baseNeighbor = tri.rightNeighbor;
		tri.rightChild.rightNeighbor = tri.leftChild;

		if(tri.leftNeighbor !is null){
			if(tri.leftNeighbor.baseNeighbor == tri)
				tri.leftNeighbor.baseNeighbor = tri.leftChild;
			else if(tri.leftNeighbor.leftNeighbor == tri)
				tri.leftNeighbor.leftNeighbor = tri.leftChild;
			else if(tri.leftNeighbor.rightNeighbor == tri)
				tri.leftNeighbor.rightNeighbor = tri.leftChild;
			else{}

		}

		if(tri.rightNeighbor !is null){
			if(tri.rightNeighbor.baseNeighbor == tri)
				tri.rightNeighbor.baseNeighbor = tri.rightChild;
			else if(tri.rightNeighbor.rightNeighbor == tri)
				tri.rightNeighbor.rightNeighbor = tri.rightChild;
			else if(tri.rightNeighbor.leftNeighbor == tri)
				tri.rightNeighbor.leftNeighbor = tri.rightChild;
			else{}
		}

		if (tri.baseNeighbor !is null){
			if(tri.baseNeighbor.leftChild){
				tri.baseNeighbor.leftChild.rightNeighbor = tri.rightChild;
				tri.baseNeighbor.rightChild.leftNeighbor = tri.leftChild;
				tri.leftChild.rightNeighbor = tri.baseNeighbor.rightChild;
				tri.rightChild.leftNeighbor = tri.baseNeighbor.leftChild;
			}
			else
				split(tri.baseNeighbor);
		}
		else{
			tri.leftChild.rightNeighbor = null;
			tri.rightChild.leftNeighbor = null;
		}
	}


	void recursTessellate(TriTreeNode* tri, int leftX, int leftY, int rightX, int rightY, int apexX, int apexY, int node, vec3 viewPosition, float frameVariance){
		float triVariance;
		int centerX = (leftX + rightX)>>1; // Compute X coordinate of center of Hypotenuse
		int centerY = (leftY + rightY)>>1;

		if(node < (1<<varianceDepth)){
			float distance = 1.0f + sqrt((centerX-viewPosition.x) * (centerX-viewPosition.x) + (centerY-viewPosition.z) * ((centerY-viewPosition.z)));
			triVariance = (cast(float)(currentVariance[node] * mapSize*2))/distance;
		}

		if( node>= (1<<varianceDepth) || triVariance > frameVariance){
			split(tri);
			if(tri.leftChild && (abs(leftX-rightX)>=3 || abs(leftY-rightY)>=3)){
				recursTessellate(tri.leftChild, apexX, apexY, leftX, leftY, centerX, centerY, node<<1, viewPosition, frameVariance);
				recursTessellate(tri.rightChild, rightX, rightY, apexX, apexY, centerX, centerY, 1+(node<<1), viewPosition, frameVariance);

			}
		}
	}

	void tessellate(vec3 viewPosition, float frameVariance){
		currentVariance = varianceLeft;
		recursTessellate(&baseLeft, worldX, worldY + patchSize, worldX + patchSize, worldY, worldX, worldY, 1, viewPosition, frameVariance);
		recursTessellate(&baseRight, worldX + patchSize, worldY, worldX, worldY+patchSize, worldX+patchSize, worldY+patchSize, 1, viewPosition, frameVariance);
	}

	void recursRender(TriTreeNode *tri, int leftX, int leftY, int rightX, int rightY, int apexX, int apexY){

		if(tri.leftChild !is null){
			int centerX = (leftX + rightX)>>1;
			int centerY = (leftY + rightY)>>1;

			recursRender(tri.leftChild, apexX, apexY, leftX, leftY, centerX, centerY);
			recursRender(tri.rightChild, rightX, rightY, apexX, apexY, centerX, centerY);
		}
		else{
			float leftZ = heightMap[(leftY * mapSize)+leftX ];
			float rightZ = heightMap[(rightY * mapSize)+rightX];
			float apexZ = heightMap[(apexY * mapSize)+apexX ];

			renderer.drawTriangle(leftX, leftZ, leftY, rightX, rightZ, rightY, apexX, apexZ, apexY);
		}
	}

	void render(){
		renderer.initPatch(cast(float)worldX, cast(float)worldY);

		recursRender(&baseLeft, 0, patchSize, patchSize, 0, 0,	0);
		recursRender(&baseRight, patchSize,	0, 0, patchSize, patchSize, patchSize);
		
		renderer.endPatch();	
	}

	private {
		ubyte*		heightMap;
		int			worldX;
		int			worldY;

		int			varianceDepth;
		int			mapSize;
		int			patchSize;

		ubyte*		varianceLeft;
		ubyte*		varianceRight;

		ubyte*		currentVariance;

		TriPool		triPool;
	}
	public{
		TriTreeNode baseLeft;
		TriTreeNode baseRight;
		
		bool		visible;
		bool		varianceDirty;
	}
}
